package lab4;

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class ClosestPair {
	private static ArrayList<Point2D> Px;
	private static ArrayList<Point2D> Py;

	public static void main(String[] args) {
		long startTime  = System.currentTimeMillis();
		Px = new ArrayList<Point2D>();
		Py = new ArrayList<Point2D>();

		try {
			FileInputStream is = new FileInputStream(args[0]);
			FileInputStream is2;
			BufferedReader br = new BufferedReader(new InputStreamReader(is));
			BufferedReader br2;
			Point2D point;

			String line = "";
			String[] str1;
			String[] str2;
			br.skip(8);

			while ((line = br.readLine()) != null) {
				Px.clear();
				Py.clear();
				str1 = line.split(": | ");
				System.out.println(str1[0]);
				// System.out.println(str1[1]);
				// System.out.println(str1[2]);
				is2 = new FileInputStream(str1[0]);
				br2 = new BufferedReader(new InputStreamReader(is2));
				while (!(line = br2.readLine()).contains("NODE_COORD_SECTION")) {
				}
				
				while ((line = br2.readLine()) != null && !line.equals("") && !line.contains("EOF")) {
					str2 = line.split("       |      |     |    |   |  | ");
					
					if (str2[0].equals("")) {
						point = new Point2D.Double(Double.parseDouble(str2[2]),
								Double.parseDouble(str2[3]));
					} else {
						point = new Point2D.Double(Double.parseDouble(str2[1]),
								Double.parseDouble(str2[2]));
					}
					
					Px.add(point);
					Py.add(point);
				}
				
				System.out.println("difference: "
						+ (shortestDistance() - Double.parseDouble(str1[2]))
						+ "\n");
				br.skip(8);
			}
		} catch (IOException e) {
			e.printStackTrace();
		} catch (NullPointerException e) {
			e.printStackTrace();
		}
		
		System.out.println("\nRunning time: " + (System.currentTimeMillis() - startTime) + "ms");

		// Point2D.Double p1 = new Point2D.Double(1, 1);
		// Point2D.Double p2 = new Point2D.Double(3, -1);
		// Point2D.Double p3 = new Point2D.Double(0.5, 4);
		// Point2D.Double p4 = new Point2D.Double(7, 8);
		//
		// Px.add(p1);
		// Px.add(p2);
		// Px.add(p3);
		// Px.add(p4);
		// Py.add(p1);
		// Py.add(p2);
		// Py.add(p3);
		// Py.add(p4);

	}

	private static double shortestDistance() {
		Collections.sort(Px, new XComparator());
		Collections.sort(Py, new YComparator());

//		System.out.println("Px");
//		for (Point2D p : Px) {
//			System.out.println(p.getX());
//		}
//
//		System.out.println("Py");
//		for (Point2D p : Py) {
//			System.out.println(p.getY());
//		}

		PointPair closestPair = closestPairRec(Px, Py);
		System.out.println("x1:" + closestPair.getP1().getX() + " y1:"
				+ closestPair.getP1().getY() + " x2:"
				+ closestPair.getP2().getX() + " y2:"
				+ closestPair.getP2().getY() + " distance:"
				+ closestPair.distance());

		return closestPair.distance();
	}

	private static PointPair closestPairRec(List<Point2D> X, List<Point2D> Y) {
		if (X.size() <= 3) {
			PointPair pair = new PointPair(X.get(0), X.get(1));
			if (X.size() == 3) {
				if (X.get(0).distance(X.get(2)) < pair.distance())
					pair = new PointPair(X.get(0), X.get(2));

				if (X.get(1).distance(X.get(2)) < pair.distance())
					pair = new PointPair(X.get(1), X.get(2));
			}

			return pair;
		}

		List<Point2D> Qx = new ArrayList<Point2D>();
		List<Point2D> Rx = new ArrayList<Point2D>();
		List<Point2D> Qy = new ArrayList<Point2D>();
		List<Point2D> Ry = new ArrayList<Point2D>();
		
		for(int i = 0; i < X.size()/2; i++) {
			Qx.add(X.get(i));
			Qy.add(X.get(i));
		}
		for(int i = X.size()/2; i < X.size(); i++) {
			Rx.add(X.get(i));
			Ry.add(X.get(i));
		}
		
		Collections.sort(Qy, new YComparator());
		Collections.sort(Ry, new YComparator());
		
		
//		System.out.println("Qx");
//		for (Point2D p : Qx) {
//			System.out.println(p.getX());
//		}
//		System.out.println("Rx");
//		for (Point2D p : Rx) {
//			System.out.println(p.getX());
//		}
		PointPair Qpair = closestPairRec(Qx, Qy);
		PointPair Rpair = closestPairRec(Rx, Ry);

		double delta = Qpair.minDistance(Rpair);
		double x = Qx.get(Qx.size() - 1).getX(); // Maximum x-coordinate of a
													// point in set Q

		ArrayList<Point2D> Sy = new ArrayList<Point2D>();
		for (Point2D p : Y) {
			if (Math.abs(x - p.getX()) < delta)
				Sy.add(p);
		}

		PointPair Spair = null;
		if (Sy.size() > 1) {
			Spair = new PointPair(Sy.get(0), Sy.get(1));
			for (int i = 0; i < Sy.size(); i++) {
				for (int j = i + 1; j <= i + 8 && j < Sy.size(); j++) {
					if (Sy.get(i).distance(Sy.get(j)) < Spair.distance())
						Spair = new PointPair(Sy.get(i), Sy.get(j));
				}
			}
		}

		if (Spair != null && Spair.distance() < delta) {
			return Spair;
		} else if (Qpair.distance() < Rpair.distance()) {
			return Qpair;
		} else {
			return Rpair;
		}
	}

}
